/***************************************
* 3．编写程序实现用三元组表示的稀疏数组的输入、转置、输出。
* 可以直接输入三元组，转置基于三元组进行，输出的结果要求：
* 1) 打印原始输入的三元组及对应的矩阵形式；
* 2) 打印转置后的三元组及对应的矩阵形式。
* 3) 按矩阵形式打印时不得将三元组转换成二维数组形式存储。
****************************************************/


#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct {int col,row,data;} triple;

void display_sparse_mat_table(const triple* m){
    printf("<SparseMatrix %dx%d with %d element%s>\n",m->row,m->col,m->data,m->data>1?"s":"");
    if(m->data)printf(" row| col|data\n");
    for(int i=1;i<=m->data;i++)
        printf("%4d|%4d|%4d\n",m[i].row,m[i].col,m[i].data);
}

void print_sparse_mat_as_mat(const triple* m){
    int i,j,k = 1;
    printf("<SparseMatrix %dx%d>\n",m->row,m->col);
    for(i=0;i<m->row;i++){
        for(j=0;j<m->col;j++){
            if(k<=m->data && m[k].row==i+1 && m[k].col == j+1)
                printf("%4d ",m[k++].data);
            else printf("   0 ");
        }
        putchar('\n');
    }
}


triple* fast_transpose(const triple* m){
    int* idx = malloc(sizeof(int)* m->col);
    int* pos = malloc(sizeof(int)* m->col);
    triple* t = malloc(sizeof(triple)*(m->data+1));
    t->data = m->data; t->col = m->col; t->row = m->row;
    memset(idx,0,sizeof(int)*m->col);
    pos[0]=1;
    int i,j,k;
    for(i=0;i<m->data;i++)idx[m[i+1].col-1]++;
    for(i=1;i<m->col;i++)pos[i] = pos[i-1]+ idx[i-1];
    for(i=0;i<m->data;i++){
        j = pos[ m[i+1].col-1 ]++;
        t[j].row = m[i+1].col;
        t[j].col = m[i+1].row;
        t[j].data = m[i+1].data;
    }
    free(idx);free(pos);
    return t;
}

int main(){
    int i,j,k;
    triple* mat_a;
    printf("Enter sparse matrix size, row,col,and mnumber of non-zero elements: ");
    scanf("%d%d%d",&i,&j,&k);
    mat_a = malloc(sizeof(triple)*(k+1));
    mat_a->row = i;
    mat_a->col = j;
    mat_a->data = k;
    printf("Enter mat elements: row,col,data \n");
    for(i=1;i<=mat_a->data;i++){
        printf("Element #%d> ",i);
        scanf("%d%d%d",&mat_a[i].row,&mat_a[i].col,&mat_a[i].data);
        fflush(stdin);
    }
    display_sparse_mat_table(mat_a);
    print_sparse_mat_as_mat(mat_a);

    triple* mat_b = fast_transpose(mat_a);
    printf("Transpose: ");
    display_sparse_mat_table(mat_b);
    print_sparse_mat_as_mat(mat_b);

    free(mat_a);
    free(mat_b);
    return 0;
}
